Two-party general secure function evaluation (SFE) allows two parties to evaluate any function on their respective inputs x and y, while maintaining the privacy of both x and y. Efficient SFE algorithms enable a variety of electronic transactions, previously impossible due to mutual mistrust of participants. For example, SFE, algorithms have been employed in auctions, contract signing and distributed database mining applications. As computation and communication resources have increased, SFE has become truly practical for common use. A malicious SFE model provides a guarantee of complete privacy of the players' inputs, even when a dishonest player follows an arbitrary cheating strategy. A semi-honest SFE model assumes that the parties follow the protocol, but attempt to learn the input of the other party.
Existing generic two-party SFE algorithms typically employ Garbled Circuits (GCs). For a detailed discussion of GCs, see, for example, Y. Lindell and B. Pinkas, “A Proof of Yao's Protocol for Secure Two-Party Computation,” Journal of Cryptology, 22(2):161-188 (2009). For reasonably complex functions, however, the data transfer required for SFE is prohibitive. In fact, the communication complexity of GC-based SFE protocols is dominated by the size of the GC, which can reach Megabytes or Gigabytes even for relatively small and simple functions (e.g., the GC for a single secure evaluation of the block cipher AES has size 0.5 Megabytes).
While transmission of large amounts of data is often possible, existing networks will not scale should SFE be widely deployed. This is particularly true for wireless networks, or for larger scale deployment of secure computations, e.g., by banks or service providers, with a large number of customers. Additional obstacles include energy consumption required to transmit/receive the data, and the resulting reduced battery life in mobile clients, such as smartphones. Computational load on the server is also a significant problem. Moreover, security against more powerful malicious adversaries requires the use of the standard cut-and-choose technique, which in turn requires transfer of multiple GCs.
A need remains for improved techniques for secure function evaluation where both parties are assumed to be semi-honest.